(1) Technical Field
The present invention relates to techniques for security and fault tolerance in hybrid networks. Specifically, the invention relates to a system and method to allow and utilize multiple Cross Layer Communication Agents in a single sub-network for increased fault tolerance.
(2) Discussion
Over the past several decades, the electronic communications field, particularly in the area of wireless communication, has exploded. Wireless communication is no longer limited to terrestrial networks, such as cellular networks; instead, the field has expanded to include hybrid networks such as satellite networks combined with fixed and mobile multi-hop terrestrial networks. FIG. 1 depicts a hybrid network 100 comprising different components such as ad-hoc sub-networks 102, 104 and low earth orbiting (LEO) or geostationary earth orbiting (GEO) satellites 106.
In order to enable connectivity between the disparate components, cross layer communication agents (CCAs) 108-1, 108-2 are used. CCAs 108-1, 108-2 serve as gateways capable of interfacing with the various hybrid components of the hybrid network 100. Typically hybrid networks comprise different network types such as satellite networks, fixed, and mobile networks all interconnected though a variety of CCAs. The CCAs can switch packets between different networks and thus enable communication between the different components.
The concept of CCAs becomes even more complicated when applied to an ad-hoc network. An ad-hoc network comprises many mobile nodes that communicate using transceivers capable of transmitting or receiving short-range signals. Some of these mobile nodes function as CCAs since they are equipped with communication equipment capable of transmitting to other realms, such as satellite transmitters/receivers. Therefore, all communication from the ad-hoc network to the other components within the heterogeneous network 100 has to be routed through the CCA nodes 108-1, 108-2. For example, if a node 102-1 in an ad-hoc network 102 wishes to send data to a node 104-1 in another ad-hoc network 104 that is a part of the heterogeneous network 100, node 102-1 has to first route the data packets to a CCA 108-1. The CCA 108-1 will then forward the data packets to a satellite 106 which will forward the packets to a CCA 108-2 in the destination ad-hoc network 104, which forwards the packets to the destination node 104-1. However, for this chain of events to execute successfully, each node 102-1, 104-1 in the heterogeneous network 100 needs to be configured with the information for identifying its affiliated CCA 108. If only a single CCA 108 is present in each ad-hoc network 102, 104, then the job of configuring each node 102-1, 104-1 with CCA information is not difficult. Just as in a wired local area network (LAN), the mobile nodes can be configured either manually or during IP address assignment using dynamic host configuration protocol (DHCP).
From a fault tolerance point of view, the foregoing network architecture, where there is only one CCA, presents a problem. If the one CCA fails, then the entire ad-hoc network associated with that CCA will be disconnected from the heterogeneous network 100. To reduce the potential for complete disconnection of an ad-hoc network due to a failure of a single component, it is desirable that each ad-hoc network have multiple, redundant CCAs. Furthermore, all CCAs may not be able to communicate with LEO satellites at all times for various reasons, such as terrain blockages, buffer overflows, etc. In these cases, it is desirable to have at least one other CCA-capable node to take over the responsibility of being the gateway CCA for the group. However to facilitate CCA redundancy, a need exists to coordinate the relay of data to these multiple CCA-capable nodes within a single ad-hoc network. First, communication is necessary to determine which CCA-capable node is going to be the gateway. Second, all other nodes in the ad-hoc network need to be informed which CCA-capable node is the current gateway CCA. So when one CCA-capable node takes over the responsibility of being the gateway CCA for the group, the mobile nodes within its purview need to be informed to route their inter-domain packets to the new gateway CCA. However, standard Internet inter-domain routing protocols, such as border gateway protocol (BGP) are not useful in these cases because of the high frequency of changes that occur in ad-hoc networks. Thus, what is needed is a system and method for configuring the mobile nodes with the gateway CCA information in the face of different types of faults that can occur within the ad-hoc network. Typically these faults include, (i) Fail-Stop: This happens when a gateway CCA is destroyed or otherwise incapacitated; (ii) Intermittent: This can occur when a gateway CCA is disabled temporarily because of terrain blockages, etc.; and (iii) Byzantine: This happens when a gateway CCA is confiscated and is being manipulated by an unknown entity (i.e. a hacker or some other enemy).
(3) Related Work
Several routing protocols, e.g., dynamic source routing (DSR), destination-sequenced distance vector (DSDV) and temporally ordered routing algorithm (TORA), have been proposed for ad-hoc networks. Almost all of these algorithms are for routing within the ad-hoc network only. They do not extend to heterogeneous networks containing a mix of both ad-hoc components and infrastructure-based networks. As previously discussed, the ad-hoc network preferably has multiple CCA-capable nodes present within the ad-hoc sub-network that are capable of routing packets between the ad-hoc sub-network and the other networks comprising the heterogeneous network, i.e. fixed, satellite or airborne networks. Anycasting is a possible solution, where all the CCA-capable nodes can be grouped into a single anycast address and mobile nodes can use this address as the router for communicating with hosts not in their ad-hoc sub-network. But not all routing protocols support such anycast mechanisms. In Y. Kao and N. H. Vaiday, Anycasting and Geo-casting in Mobile Ad-hoc Networks, Technical Report TR00-014, Department of Computer Sciences, Texas A&M University, 27, 2000, Vaiday et al. propose extensions to TORA to support anycasting. Further, in C. Intanagonwiwat and D. D. Lucia, The Sink-based Anycast Routing Protocol for Ad-hoc Wireless Sensor Networks, Technical Report 99-698, USC/Information Sciences Institute, 1990, a sink-based anycast routing protocol is proposed.
There has been little research in the area of security and fault tolerance for ad-hoc networks. In L. Zhou and Z. Hass, Securing Ad-hoc Networks, IEEE Network Magazine, 13(6), 1999, security-related issues involving routing in ad-hoc networks are discussed. The Hass et al. article proposes that ad-hoc networks should have a distributed architecture with no central entities to achieve high survivability. They propose to use (n, t+1) threshold cryptographic methods to decentralize any cryptographic operation (e.g., signing a key), where at least t+1 nodes have to collaborate to perform the operation and no set of t nodes can achieve the same result, even operating in collusion.
Any fault-tolerant algorithm inherently has to be distributed. The complexity of such algorithms in ad-hoc networks is increased due to the highly dynamic nature of such networks and the unreliability of the communication medium. In K. P. Hatzis, G. P. Pentaris, P. G. Spirakis, V. T. Tampakas, and R. B. Tan, Fundamental Control Algorithms in Mobile Networks, ACM Symposium on Parallel Algorithms and Architectures, p. 251-260, 1999, the authors propose two distributed leader election algorithms for ad-hoc networks. Their algorithms require that all nodes know the coordinates of the space in advance. In N. Malpani, J. L. Welch, and N. Vaida, Leader Election Algorithms for Mobile Ad-hoc Networks, Proceedings of the 4th International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, p. 96-103, Boston, Mass., August 2000, the authors propose distributed leader election algorithms that are based on TORA. However, both of these works consider only the dynamic and multi-hop nature of the mobile ad-hoc network and assume that the communication medium is reliable and that the nodes are ‘well-behaved.’
Other distributed problems solved for mobile ad-hoc networks are mutual exclusion in J. Walter, J. Welch, and N. H. Vaida, A Mutual Exclusion Algorithm for Ad-hoc Mobile Networks, Technical Report TR99-011, Department of Computer Sciences, Texas A&M University, 1999 and reliable broadcast in E. Pagani and G. P. Rossi, Reliable Broadcast in Mobile Multi-hop Packet Networks, Mobile Computing and Networking, pg. 34-42, 1997. None of these works deals with the case of misbehaving nodes.